
from typing import List
from functools import cache

# 记忆化搜索
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # 记忆化搜索，存储已经计算过的和对应的组合数量
        # 组合问题，每个元素可以多选，每次从第一个元素开始遍历
        @cache
        def dfs(cnt):
            # 当当前组合的和等于目标值时，找到一种有效组合，返回 1
            if cnt == target:
                return 1
            # 当当前组合的和超过目标值时，此组合无效，返回 0
            if cnt > target:
                return 0
            # 初始化组合数量为 0
            total = 0
            # 遍历数组中的每个元素
            for num in nums:
                # 递归计算选择当前元素后剩余和的组合数量，并累加到总数中
                total += dfs(cnt + num)
            return total

        # 从和为 0 开始递归计算
        return dfs(0)


